home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Internet Surfer: Getting Started
/
Internet Surfer - Getting Started (Wayzata Technology)(7231)(1995).bin
/
pc
/
textfile
/
mac_faqs
/
puzz_faq
/
part10
< prev
next >
Wrap
Internet Message Format
|
1995-01-30
|
61KB
Xref: bloom-picayune.mit.edu rec.puzzles:18145 news.answers:3076
Newsgroups: rec.puzzles,news.answers
Path: bloom-picayune.mit.edu!enterpoop.mit.edu!snorkelwacker.mit.edu!usc!wupost!spool.mu.edu!uunet!questrel!chris
From: uunet!questrel!chris (Chris Cole)
Subject: rec.puzzles FAQ, part 10 of 15
Message-ID: <puzzles-faq-10_717034101@questrel.com>
Followup-To: rec.puzzles
Summary: This posting contains a list of
Frequently Asked Questions (and their answers).
It should be read by anyone who wishes to
post to the rec.puzzles newsgroup.
Sender: chris@questrel.com (Chris Cole)
Reply-To: uunet!questrel!faql-comment
Organization: Questrel, Inc.
References: <puzzles-faq-1_717034101@questrel.com>
Date: Mon, 21 Sep 1992 00:09:31 GMT
Approved: news-answers-request@MIT.Edu
Expires: Sat, 3 Apr 1993 00:08:21 GMT
Lines: 1487
Archive-name: puzzles-faq/part10
Last-modified: 1992/09/20
Version: 3
==> games/square-1.s <==
SHAPES
1. There are 29 different shapes for a side, counting reflections:
1 with 6 corners, 0 edges
3 with 5 corners, 2 edges
10 with 4 corners, 4 edges
10 with 3 corners, 6 edges
5 with 2 corners, 8 edges
2. Naturally, a surplus of corners on one side must be compensated
by a deficit of corners on the other side. Thus there are 1*5 +
3*10 + C(10,2) = 5 + 30 + 55 = 90 distinct combinations of shapes,
not counting the middle layer.
3. You can reach two squares from any other shape in at most 7 transforms,
where a transform consists of (1) optionally twisting the top, (2)
optionally twisting the bottom, and (3) flipping.
4. Each transform toggles the middle layer between Square and Kite,
so you may need 8 transforms to reach a perfect cube.
5. The shapes with 4 corners and 4 edges on each side fall into four
mutually separated classes. Side shapes can be assigned values:
0: Square, Mushroom, and Shield; 1: Left Fist and Left Paw; 2:
Scallop, Kite, and Barrel; 3. Right Fist and Right Paw. The top
and bottom's sum or difference, depending on how you look at them,
is a constant. Notice that the side shapes with bilateral symmetry
are those with even values.
6. To change this constant, and in particular to make it zero, you must
attain a position that does not have 4 corners and 4 edges on each
side. Almost any such position will do, but returning to 4 corners
and 4 edges with the right constant is left to your ingenuity.
7. If the top and bottom are Squares but the middle is a Kite, just flip
with the top and bottom 30deg out of phase and you will get a cube.
COLORS
1. I do not know the most efficient way to restore the colors. What
follows is my own suboptimal method. All flips keep the yellow
stripe steady and flip the blue stripe.
2. You can permute the corners without changing the edges, so first
get the edges right, then the corners.
3. This transformation sends the right top edge to the bottom
and the left bottom edge to the top, leaving the other edges
on the same side as they started: Twist top 30deg cl, flip,
twist top 30deg ccl, twist bottom 150deg cl, flip, twist bottom
30deg cl, twist top 120deg cl, flip, twist top 30deg ccl, twist
bottom 150deg cl, flip, twist bottom 30deg cl. Cl and ccl are
defined looking directly at the face. With this transformation
you can eventually get all the white edges on top.
4. Check the parity of the edge sequence on each side. If either is
wrong, you need to fix it. Sorry -- I don't know how! (See any
standard reference on combinatorics for an explanation of parity.)
5. The following transformation cyclically permutes ccl all the top edges
but the right one and cl all the bottom edges but the left one. Apply
the transformation in 3., and turn the whole cube 180deg. Repeat.
This is a useful transformation, though not a cure-all.
6. Varying the transformation in 3. with other twists will produce other
results.
7. The following transformation changes a cube into a Comet and Star:
Flip to get Kite and Kite. Twist top and bottom cl 90deg and flip to get
Barrel and Barrel. Twist top cl 30 and bottom cl 60 and flip to get
Scallop and Scallop. Twist top cl 60 and bottom cl 120 and flip to
get Comet and Star. The virtue of the Star is that it contains only
corners, so that you can permute the corners without altering the edges.
8. To reach a Lemon and Star instead, replace the final bottom cl 120 with
a bottom cl 60. In both these transformation the Star is on the bottom.
9. The following transformation cyclically permutes all but the bottom
left rear. It sends the top left front to the bottom, and the bottom
left front to the top. Go to Comet and Star. Twist star cl 60.
Go to Lemon and Star -- you need not return all the way to the cube, but
do it if you're unsure of yourself by following 7 backwards. Twist star
cl 60. Return to cube by following 8 backwards. With this transformation
you should be able to get all the white corners on top.
10. Check the parity of the corner sequences on both sides. If the bottom
parity is wrong, here's how to fix it: Go to Lemon and Star. The
colors on the Star will run WWGWWG. Twist it 180 and return to cube.
11. If the top parity is wrong, do the same thing, except that when you
go from Scallop and Scallop to Lemon and Star, twist the top and bottom
ccl instead of cl. The colors on the Star should now run GGWGGW.
12. Once the parity is right on both sides, the basic method is to
go to Comet and Star, twist the star 120 cl (it will be WGWGWG),
return to cube, twist one or both sides, go to Comet and Star,
undo the star twist, return to cube, undo the side twists.
With no side twists, this does nothing. If you twist the top,
you will permute the top corners. If you twist the bottom,
you will permute the bottom corners. Eventually you will get
both the top and the bottom right. Don't forget to undo the
side twists -- you need to have the edges in the right places.
Happy twisting....
--
Col. G. L. Sicherman
gls@windmill.att.COM
==> games/think.and.jump.p <==
THINK & JUMP: FIRST THINK, THEN JUMP UNTIL YOU
ARE LEFT WITH ONE PEG! O - O O - O
/ \ / \ / \ / \
O---O---O---O---O
BOARD DESCRIPTION: To the right is a model of \ / \ / \ / \ /
the Think & Jump board. The O---O---O---O---O---O
O's represent holes which / \ / \ / \ / \ / \ / \
contain pegs. O---O---O---O---O---O---O
\ / \ / \ / \ / \ / \ /
O---O---O---O---O---O
DIRECTIONS: To play this brain teaser, you begin / \ / \ / \ / \
by removing the center peg. Then, O---O---O---O---O
moving any direction in the grid, \ / \ / \ / \ /
jump over one peg at a time, O - O O - O
removing the jumped peg - until only
one peg is left. It's harder then it looks.
But it's more fun than you can imagine.
SKILL CHART:
10 pegs left - getting better
5 pegs left - true talent
1 peg left - you're a genius
Manufactured by Pressman Toy Corporation, NY, NY.
==> games/think.and.jump.s <==
Three-color the board in the obvious way. The initial configuration has 12
of each color, and each jump changes the parity of all three colors. Thus,
it is impossible to achieve any position where the colors do not have the
same parity; in particular, (1,0,0).
If you remove the requirement that the initially-empty cell must be at the
center, the game becomes solvable. The demonstration is left as an exercise.
Karl Heuer rutgers!harvard!ima!haddock!karl karl@haddock.ima.isc.com
Here is one way of reducing Think & Jump to two pegs.
Long simplifies Balsley's scintillating snowflake solution:
1 U-S A - B C - D
2 H-U / \ / \ / \ / \
3 V-T E---F---G---H---I
4 S-H \ / \ / \ / \ /
5 D-M J---K---L---M---N---O
6 F-S / \ / \ / \ / \ / \ / \
7 Q-F P---Q---R---S---T---U---V
8 A-L \ / \ / \ / \ / \ / \ /
9 S-Q W---X---Y---Z---a---b
10 P-R / \ / \ / \ / \
11 Z-N c---d---e---f---g
12 Y-K \ / \ / \ / \ /
13 h-Y h - i j - k
14 k-Z
The board should now be in the snowflake pattern, i.e. look like
o - * * - o
/ \ / \ / \ / \
*---o---*---o---*
\ / \ / \ / \ /
*---*---*---*---*---*
/ \ / \ / \ / \ / \ / \
o---o---o---o---o---o---o
\ / \ / \ / \ / \ / \ /
*---*---*---*---*---*
/ \ / \ / \ / \
*---o---*---o---*
\ / \ / \ / \ /
o - * * - o
where o is empty and * is a peg. The top and bottom can now be reduced
to single pegs individually. For example, we could continue
15 g-T
16 Y-a
17 i-Z
18 T-e
19 j-Y
20 b-Z
21 c-R
22 Z-X
23 W-Y
24 R-e
which finishes the bottom. The top can be done in a similar manner.
--
Chris Long
==> games/tictactoe.p <==
In random tic-tac-toe, what is the probability that the first mover wins?
==> games/tictactoe.s <==
Count cases.
First assume that the game goes on even after a win. (Later figure
out who won if each player gets a row of three.) Then there are
9!/5!4! possible final boards, of which
8*6!/2!4! - 2*6*4!/0!4! - 3*3*4!/0!4! - 1 = 98
have a row of three Xs. The first term is 8 rows times (6 choose 2)
ways to put down the remaining 2 Xs. The second term is the number
of ways X can have a diagonal row plus a horizontal or vertical row.
The third term is the number of ways X can have a vertical and a
horizontal row, and the 4th term is the number of ways X can have two
diagonal rows. All the two-row configurations must be subtracted to
avoid double-counting.
There are 8*6!/1!5! = 48 ways O can get a row. There is no double-
counting problem since only 4 Os are on the final board.
There are 6*2*3!/2!1! = 36 ways that both players can have a
row. (6 possible rows for X, each leaving 2 possible rows for O
and (3 choose 2) ways to arrange the remaining row.) These
cases need further consideration.
There are 98 - 36 = 62 ways X can have a row but not O.
There are 48 - 36 = 12 ways O can have a row but not X.
There are 126 - 36 - 62 - 12 = 16 ways the game can be a tie.
Now consider the 36 configurations in which each player has a row.
Each such can be achieved in 5!4! = 2880 orders. There are 3*4!4!
= 1728 ways that X's last move completes his row. In these cases O
wins. There are 2*3*3!3! = 216 ways that Xs fourth move completes
his row and Os row is already done in three moves. In these cases O
also wins. Altogether, O wins 1728 + 216 = 1944 out of 2880 times
in each of these 36 configurations. X wins the other 936 out of
2880.
Altogether, the probability of X winning is ( 62 + 36*(936/2880) ) / 126.
win: 737 / 1260 ( 0.5849206... )
lose: 121 / 420 ( 0.2880952... )
draw: 8 / 63 ( 0.1269841... )
1000000 games: won 584865, lost 288240, tied 126895
Instead, how about just methodically having the program play every
possible game, tallying up who wins?
Wonderful idea, especially since there are only 9! ~ 1/3 million
possible games. Of course some are identical because they end in
fewer than 8 moves. It is clear that these should be counted
multiple times since they are more probable than games that go
longer.
The result:
362880 games: won 212256, lost 104544, tied 46080
#include <stdio.h>
int board[9];
int N, move, won, lost, tied;
int perm[9] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
int rows[8][3] = {
{ 0, 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 }, { 0, 3, 6 },
{ 1, 4, 7 }, { 2, 5, 8 }, { 0, 4, 8 }, { 2, 4, 6 }
};
main()
{
do {
bzero((char *)board, sizeof board);
for ( move=0; move<9; move++ ) {
board[perm[move]] = (move&1) ? 4 : 1;
if ( move >= 4 && over() )
break;
}
if ( move == 9 )
tied++;
#ifdef DEBUG
printf("%1d%1d%1d\n%1d%1d%1d w %d, l %d, t %d\n%1d%1d%1d\n\n",
board[0], board[1], board[2],
board[3], board[4], board[5], won, lost, tied,
board[6], board[7], board[8]);
#endif
N++;
} while ( nextperm(perm, 9) );
printf("%d games: won %d, lost %d, tied %d\n", N, won, lost, tied);
exit(0);
}
int s;
int *row;
over()
{
for ( row=rows[0]; row<rows[8]; row+=3 ) {
s = board[row[0]] + board[row[1]] + board[row[2]];
if ( s == 3 )
return ++won;
if ( s == 12 )
return ++lost;
}
return 0;
}
nextperm(c, n)
int c[], n;
{
int i = n-2, j=n-1, t;
while ( i >= 0 && c[i] >= c[i+1] )
i--;
if ( i < 0 )
return 0;
while ( c[j] <= c[i] )
j--;
t = c[i]; c[i] = c[j]; c[j] = t;
i++; j = n-1;
while ( i < j ) {
t = c[i]; c[i] = c[j]; c[j] = t;
i++; j--;
}
return 1;
}
==> geometry/K3,3.p <==
Can three houses be connected to three utilities without the pipes crossing?
_______ _______ _______
| oil | |water| | gas |
|_____| |_____| |_____|
_______ _______ _______
|HOUSE| |HOUSE| |HOUSE|
| one | | two | |three|
==> geometry/K3,3.s <==
The problem you describe is to draw a bipartite graph of 3 nodes connected
in all ways to 3 nodes, all embedded in the plane. The graph is called K3,3.
A famous theorem of Kuratowsky says that all graphs can be embedded
in the plane, EXCEPT those containing K3,3 or K5 (the complete graph
on 5 vertices, i.e., the graph with 5 nodes and 10 edges) as a
subgraph. So your problem is a minimal example of a graph that
cannot be embedded in the plane.
The proofs that K5 and K3,3 are non-planar are really quite easy, and only
depend on Euler's Theorem that F-E+V=2 for a planar graph.
For K3,3 V is 6 and E is 9, so F would have to be 5. But each face has at
least 4 edges, so E >= (F*4)/2 = 10, contradiction.
For K5 V is 5 and E is 10, so F = 7. In this case each face has at least 3
edges, so E >= (F*3)/2 = 10.5, contradiction.
The difficult part of Kuratowsky is the proof in the other direction!
A quick, informal proof by contradiction without assuming Euler's Theorem:
Using a map in which the houses are 1, 2, and 3 and the utilities are
A, B, and C, there must be continuous lines that connect the buildings and
divide the area into three sections bounded by the loops A-1-B-2-A,
A-1-B-3-A, and A-2-B-3-A. (One of the areas is the infinite plane *around*
whichever loop is the outer edge of the network.) C must be in one of these
three areas; whichever area it is in, either 1, or 2, or 3, is *not* part of
the loop that rings its area and hence is inaccessible to C.
The usual quibble is to solve the puzzle by running one of the pipes
underneath one of houses on its way to another house; the puzzle's
instructions forbid crossing other *pipes*, but not crossing other *houses*.
==> geometry/bear.p <==
If a hunter goes out his front door, goes 50 miles south, then goes 50
miles west, shoots a bear, goes 50 miles north and ends up in front of
his house. What color was the bear?
==> geometry/bear.s <==
The hunter's door is in one of two locations. One is a foot or so from the
North Pole, facing north, such that his position in front of the door is
precisely upon the North Pole. Since that's a ridiculous place to build a
house and since bears do not roam within fifty miles of the pole, the bear
is either imaginary or imported, and there is no telling what color it is.
There is another place (actually a whole set) on earth from which one can go
fifty miles south, fifty miles west, and fifty miles north and end up where
one started. Consider the parallel of latitude close enough to the South
Pole that the circumference of the earth at that latitude is 50/n miles,
for some integer n.
Take any point on that parallel of latitude and pick the point fifty miles
north of it. Situate the hunter's front porch there. The hunter goes fifty
miles south from his porch and is at a point we'll call A. He travels fifty
miles west, going n times around the earth, and is at A again, where he shoots
the bear. Fifty miles north from A he is back home. Since bears are not
indigenous to the Antarctic, again the bear is either imaginary or imported
and there is no telling what color it might be.
==> geometry/bisector.p <==
If two angle bisectors of a triangle are equal, then the triangle is
isosceles (more specifically, the sides opposite to the two angles
being bisected are equal).
==> geometry/bisector.s <==
The following proof is probably from Altshiller-Court's College
Geometry, since that's where I first saw the problem.
Let the triangle be ABC, with angle bisectors BE and CD.
Let F be such that BEFD is a parallelagram.
Let x = measure of angle CBE = angle DBE,
y = measure of angle BCD = angle DCE,
x' = measure of angle EFC,
y' = measure of angle ECF.
(You will probably want to draw a picture.)
Suppose x > y. Consider the triangles EBC and DCB. Since BC = BC and
BE = CD, we must have CE > BD. Now, since BD = EF, we have that CE >
EF, so that x' > y'. Thus x+x' > y+y'. But, triangle FDC is
isosceles, since DF = BE = DC, so x+x' = y+y', a contradiction.
Similarly, we cannot have x < y. Therefore the base angles of ABC are
equal, making ABC an isosceles triangle. QED
==> geometry/calendar.p <==
Build a calendar from two sets of cubes. On the first set,
spell the months with a letter on each face of three cubes.
Use lowercase three-letter abbreviations for the names of all
twelve months (e.g., "jan", "feb", "mar"). On the second set,
number the days with a digit on each face of two cubes (e.g.,
"01", "02", etc.).
==> geometry/calendar.s <==
First note that there are *nineteen* different letters in the
month abbreviations (abcdef gjlmno prstuv y) so to get them all on the
eighteen faces of 3 cubes, you know right away you're going to have to
resort to trickery.
So I wrote them all down and looked at which ones could be
reversed to make another letter in the set. The only pair that jumped
out at me was the d/p pair. Now I knew that it was at least feasible,
as long as it wasn't necessary to duplicate any letters.
Then I scanned the abbreviations to find ones that had a lot of
common letters. The jan-jun-jul series looked like a good place to
start:
j a n
u l
was a good beginning but I realized
right away that I had no room for duplicate letters and the second cube
had both a and u so aug was going to be impossible. In fact I almost
posted that answer. Then I realized that if Martin Gardner wrote about
it, it must have a solution. :-) So I went back to the letter list.
I don't put tails on my u's so it didn't strike me the first
time through that n and u could be combined.
Cube 1 Cube 2 Cube 3
j a n/u
n/u l
would let me get away with putting the g
on the first cube to get aug, so I did.
j a n/u
g n/u l (1)
Now came the fun part. The a was placed so I had to work around
it for the other months that had an a in them (mar, apr, may).
m a r
d/p y (2)
Now the d/p was placed so I had to work around that for sep and dec.
This one was easy since they shared an e as well.
d/p e s
c (3)
Now the e was placed so feb had to be worked in.
f e b (4)
The two months left (oct, nov) were far more complex. Not only
did they have two "set" letters (c, n/u), there were two possible n/u's
to be set with. That's why I left them for last.
o t c
n/u v (5)
So now I had five pieces to fit together, so that no set would
have more than six letters in it. Trial and error provided:
j a n/u a b e
g n/u l or, c d/p g
r s m alphabetically: f l j
y c d/p n/u m o
e v t s n/u r
o f b v t y
Without some gimmick the days cannot be done. Because of the dates 11 and
22, there must be a 1 and a 2 on each cube. Thus there are 8 remaining spaces
for the 8 remaining numbers, and because of 30, we put 3 and 0 on different
cubes. I don't think the way you allocate the others matter. Now 6 numbers on
each cube can produce at most 36 distinct pairs, and we need 31 distinct pairs
to represent all possible dates. But since 3 each of {4,5,6,7,8,9} are on each
cube, there are at least 9 representable numbers which can't be dates.
Therefore there are at most 27 distinct numbers which are dates on the two
cubes, and it can't be done. In particular, not all of {04,05,06,07,08,09} can
be represented.
The gimmick solution would be to represent the numbers in a stylised format
(like say, on a digital clock or on a computer screen) such that the 6 can be
turned upside down to be a 9. Then you can have 012 on both cubes, and three
each of {3,4,5,6,7,8} on the other faces. Done.
Example: 012468 012357
==> geometry/circles.and.triangles.p <==
Find the radius of the inscribed and circumscribed circles for a triangle.
==> geometry/circles.and.triangles.s <==
Let a, b, and c be the sides of the triangle. Let s be the
semiperimeter, i.e. s = (a + b + c) / 2. Let A be the area
of the triangle, and let x be the radius of the incircle.
Divide the triangle into three smaller triangles by drawing
a line segment from each vertex to the incenter. The areas
of the smaller triangles are ax/2, bx/2, and cx/2. Thus,
A = ax/2 + bx/2 + cx/2, or A = sx.
We use Heron's formula, which is A = sqrt(s(s-a)(s-b)(s-c)).
This gives us x = sqrt((s-a)(s-b)(s-c)/s).
The radius of the circumscribed circle is given by R = abc/4A.
==> geometry/coloring/cheese.cube.p <==
A cube of cheese is divided into 27 subcubes. A mouse starts at one
corner and eats through every subcube. Can it finish in the middle?
==> geometry/coloring/cheese.cube.s <==
Give the subcubes a checkerboard-like coloring so that no two adjacent
subcubes have the same color. If the corner subcubes are black, the
cube will have 14 black subcubes and 13 white ones. The mouse always
alternates colors and so must end in a black subcube. But the center
subcube is white, so the mouse can't end there.
==> geometry/coloring/dominoes.p <==
There is a chess board (of course with 64 squares). You are given
21 dominoes of size 3-by-1 (the size of an individual square on
a chess board is 1-by-1). Which square on the chess board can
you cut out so that the 21 dominoes exactly cover the remaining
63 squares? Or is it impossible?
==> geometry/coloring/dominoes.s <==
||||||||
||||||||
||||||||
---***+*
---...+*
---*+O+*
---*+...
---*+***
There is only one way to remove a square, aside from rotations and
reflections. To see that there is at most one way, do this: Label
all the squares of the chessboard with A, B or C in sequence by rows
starting from the top:
ABCABCAB
CABCABCA
BCABCABC
ABCABCAB
CABCABCA
BCABCABC
ABCABCAB
CABCABCA
Every trimino must cover one A, one B and one C. There is one extra
A square, so an A must be removed. Now label the board again by
rows starting from the bottom:
CABCABCA
ABCABCAB
BCABCABC
CABCABCA
ABCABCAB
BCABCABC
CABCABCA
ABCABCAB
The square removed must still be an A. The only squares that got
marked with A both times are these:
........
........
..A..A..
........
........
..A..A..
........
........
==> geometry/construction/4.triangles.6.lines.p <==
Can you construct 4 equilateral triangles with 6 toothpicks?
==> geometry/construction/4.triangles.6.lines.s <==
Use the toothpicks as the edges of a tetrahedron.
==> geometry/construction/5.lines.with.4.points.p <==
Arrange 10 points so that they form 5 rows of 4 each.
==> geometry/construction/5.lines.with.4.points.s <==
Draw a 5 pointed star, put a point where any two lines meet.
==> geometry/construction/square.with.compass.p <==
Construct a square with only a compass and a straight edge.
==> geometry/construction/square.with.compass.s <==
Draw a circle (C1 at P1). Now draw a diameter D1 (intersects
at P2 and P3). Set the compass larger than before. From points P2
and P3 draw another larger circle (C2 and C3). Where these two
circles cross, draw a line (D2). This line should go the center of
circle C1 at a rt angle to the original diameter line. This line
should cross circle C1 at P4 and P5
Reset the compass to its original size. From P2 and P4 draw a circle
(C4 and C5). These circles intersect at P6 and P1. Connect P6, P2,
P1, P4 for a square.
==> geometry/cover.earth.p <==
A thin membrane covers the surface of the earth. One square meter is
added to the area of this membrane. How much is added to the radius and
volume of this membrane?
==> geometry/cover.earth.s <==
We know that V = (4/3)*pi*r^3 and A = 4*pi*r^2.
We need to find out how much V increases if A increases by 1 m^2.
dV / dr = 4 * pi * r^2
dA / dr = 8 * pi * r
dV / dA = (dV / dr) / (dA / dr)
= (4 * pi * r^2) / (8 * pi * r)
= r/2
= 3,250,000 m
If the area of the cover is increased by 1 square meter,
then the volume it contains is increased by about 3.25 million cubic meters.
We seem to be getting a lot of mileage out of such a small square of cotton.
However, the new cover would not be very high above the surface of the
planet -- about 6 nanometers (calculate dr/dA).
==> geometry/dissections/circle.p <==
Can a circle be cut into similar pieces without point symmetry
about the midpoint? Can it be done with a finite number of pieces?
==> geometry/dissections/circle.s <==
Yes. Draw a circle inside the original circle, sharing a common point
on the right. Now draw another circle inside the second, sharing a
point at the left. Now draw another inside the third, sharing a point
at the right. Continue in this way, coloring in every other region
thus generated. Now, all the colored regions touch, so count this as
one piece and the uncolored regions as a second piece. So the circle
has been divided into two similar pieces and there is no point
symmetry about the midpoint. Maybe it is cheating to call these
single pieces, though.
==> geometry/dissections/hexagon.p <==
Divide the hexagon into:
1) 3 indentical rhombuses.
2) 6 indentical kites(?).
3) 4 indentical trapezoids.
4) 8 indentcal shapes (any shape).
5) 12 identical shapes (any shape).
==> geometry/dissections/hexagon.s <==
What is considered 'identical' for these questions? If mirror-image shapes
are allowed, these are all pretty trivial. If not, the problems are rather
more difficult...
1. Connect the center to every second vertex.
2. Connect the center to the midpoint of each side.
3. This is the hard one. If you allow mirror images, it's trivial:
bisect the hexagon from vertex to vertex, then bisect with a
perpendicular to that, from midpoint of side to midpoint of side.
4. This one's neat. Let the side length of the hexagon be 2 (WLOG).
We can easily partition the hexagon into equilateral triangles
with side 2 (6 of them), which can in turn be quartered into
equilateral triangles with side 1. Thus, our original hexagon
is partitioned into 24 unit equilateral triangles. Take the
trapezoid formed by 3 of these little triangles. Place one such
trapezoid on the inside of each face of the original hexagon, so
that the long side of the trapezoid coincides with the side of the
hexagon. This uses 6 trapezoids, and leaves a unit hexagon in the
center as yet uncovered. Cover this little hexagon with two of
the trapezoids. Voila. An 8-identical-trapezoid partition.
5. Easy. Do the rhombus partition in #1. Quarter each rhombus by
connecting midpoints of opposite sides. This produces 12 small
rhombi, each of which is equivalent to two adjacent small triangles
as in #4.
Except for #3, all of these partitions can be achieved by breaking up the
hexagon into unit equilateral triangles, and then building these into the
shapes desired. For #3, though, this would require (since there are 24 small
triangles) trapezoids formed from 6 triangles each. The only trapezoid that
can be built from 6 identical triangles is a parallelogram; I assume that the
poster wouldn't have asked for a trapezoid if you could do it with a special
case of trapezoid. At any rate, that parallelogram doesn't work.
==> geometry/dissections/square.70.p <==
Since 1^2 + 2^2 + 3^2 + ... + 24^2 = 70^2, can a 70x70 sqaure be dissected into
24 squares of size 1x1, 2x2, 3x3, etc.?
==> geometry/dissections/square.70.s <==
Martin Gardner asked this in his Mathematical Games column in the
September 1966 issue of Scientific American. William Cutler was the first
of 24 readers who reduced the uncovered area to 49, using all but the 7x7
square. All the patterns were the same except for interchanging the
squares of orders 17 and 18 and rearranging the squares of orders 1, ...,
6, 8, 9, and 10. Nobody proved that the solution is minimal.
+----------------+-------------+----------------------+---------------------+
| | | | |
| | | | |
| | 11 | | |
| | | | |
| 16 | | | |
| +-----+--+----+ 22 | 21 |
| | | 2| | | |
| | 5 +--+----+ | |
| | | | | |
+----------------+--+--+ 6 | | |
| | 3| | | |
| ++-+-------+ | |
| || | ++--------------------+
| || 8 +----------------------++ |
| 18 || | | |
| || | | |
| ++---------+ | |
| | | | 20 |
| | 9 | | |
+------------------++ | 23 | |
| || | | |
| ++----------+ | |
| | | +---++---------------+
| | | | || |
| 17 | 10 | | 4 || |
| | +---------------+-------+---++ |
| +-+---------+---------------+ | 15 |
| | | | | |
| | | | 12 | |
+------------------+-+ | +-+-------------+
| | | |1| |
| | +------------+-+ |
| | 24 | | |
| | | | |
| 19 | | 13 | 14 |
| | | | |
| | | | |
| | | | |
+--------------------+-------------------------+--------------+-------------+
==> geometry/dissections/square.five.p <==
Can you dissect a square into 5 parts of equal area with just a straight edge?
==> geometry/dissections/square.five.s <==
1. Prove you can reflect points which lie on the sides of the square
about the diagonals.
2. Construct two different rectangles whose vertices lie on the square
and whose sides are parallel to the diagonals.
3. Construct points A, A', B, B' on one (extended) side of the square
such that A/A' and B/B' are mirror image pairs with respect to another
side of the square.
4. Construct the mirror image of the center of the square in one
of the sides.
5. Divide the original square into 4 equal squares whose sides are
parallel to the sides of the original square.
6. Divide one side of the square into 8 equal segments.
7. Construct a trapezoid in which one base is a square side and one
base is 5/8 of the opposite square side.
8. Divide one side of the square into 5 equal segments.
9. Divide the square into 5 equal rectangles.
==> geometry/duck.and.fox.p <==
A duck is swimming about in a circular pond. A ravenous fox (who cannot
swim) is roaming the edges of the pond, waiting for the duck to come close.
The fox can run faster than the duck can swim. In order to escape,
the duck must swim to the edge of the pond before flying away. Assume that
the duck can't fly until it has reached the edge of the pond.
How much faster must the fox run that the duck swims in order to be always
able to catch the duck?
==> geometry/duck.and.fox.s <==
Assume the ratio of the fox's speed to the duck's is a, and the radius
of the pond is r. The duck's best strategy is:
1. Swim around a circle of radius (r/a - delta) concentric with the
pond until you are diametrically opposite the fox (you, the fox, and
the center of the pond are colinear).
2. Swim a distance delta along a radial line toward the bank opposite
the fox.
3. Observe which way the fox has started to run around the circle.
Turn at a RIGHT ANGLE in the opposite direction (i.e. if you started
swimming due south in step 2 and the fox started running to the east,
i.e. clockwise around the pond, then start swimming due west). (Note:
If at the beginning of step 3 the fox is still in the same location as
at the start of step 2, i.e. directly opposite you, repeat step 2
instead of turning.)
4. While on your new course, keep track of the fox. If the fox slows
down or reverses direction, so that you again become diametrically
opposite the fox, go back to step 2. Otherwise continue in a straight
line until you reach the bank.
5. Fly away.
The duck should make delta as small as necessary in order to be able
to escape the fox.
The key to this strategy is that the duck initially follows a
radial path away from the fox until the fox commits to running either
clockwise or counterclockwise around the pond. The duck then turns onto
a new course that intersects the circle at a point MORE than halfway
around the circle from the fox's starting position. In fact, the duck
swims along a tangent of the circle of radius r/a. Let
theta = arc cos (1/a)
then the duck swims a path of length
r sin theta + delta
but the fox has to run a path of length
r*(pi + theta) - a*delta
around the circle. In the limit as delta goes to 0, the duck will
escape as long as
r*(pi + theta) < a*r sin theta
that is,
pi + arc cos (1/a) - a * sqrt(a^2 - 1) < 0
Maximize a in the above: a = 4.6033388487517003525565820291030165130674...
The fox can catch the duck as long as he can run about 4.6 times as fast as
the duck can swim.
"But wait," I hear you cry, "When the duck heads off to that spot
'more than halfway' around the circle, why doesn't the fox just double
back? That way he'll reach that spot much quicker." That is why the
duck's strategy has instructions to repeat step 2 under certain
circumstances. Note that at the end of step 2, if the fox has started
to run to head off the duck, say in a clockwise direction, he and the
duck are now on the same side of some diameter of the circle. This
continues to be true as long as both travel along their chosen paths
at full speed. But if the fox were now to try to reach the duck's
destination in a counterclockwise direction, then at some instant he
and the duck must be on a diameter of the pond. At that instant, they
have exactly returned to the situation that existed at the end of step
1, except that the duck is a little closer to the edge than she was
before. That's why the duck always repeats step 2 if the fox is ever
diametrically opposite her. Then the fox must commit again to go one
way or the other. Every time the fox fails to commit, or reverses his
commitment, the duck gets a distance delta closer to the edge. This
is a losing strategy for the fox.
The limiting ratio of velocities that this strategy works against
cannot be improved by any other strategy, i.e., if the ratio of
the duck's speed to the fox's speed is less than a then the duck
cannot escape given the best fox strategy.
Given a ratio R of speeds less than the above a, the fox is sure to
catch the duck (or keep it in water indefinitely) by pursuing the
following strategy:
Do nothing so long as the duck is in a radius of R around the centre.
As soon as it emerges from this circle, run at top speed around the
circumference. If the duck is foolish enough not to position itself
across from the center when it comes out of this circle, run "the short
way around", otherwise run in either direction.
To see this it is enough to verify that at the circumference of the
circle of radius R, all straight lines connecting the duck to points
on the circumference (in the smaller segment of the circle cut out
by the tangent to the smaller circle) bear a ratio greater than R
with the corresponding arc the fox must follow. That this is enough
follows from the observation that the shortest curve from a point on
a circle to a point on a larger concentric circle (shortest among all
curves that don't intersect the interior of the smaller circle) is
either a straight line or an arc of the smaller circle followed by a
tangential straight line.
==> geometry/earth.band.p <==
How much will a band around the equator rise above the surface if it
is made one meter longer?
==> geometry/earth.band.s <==
The formula for the circumference of a circle is 2 * pi * radius. Therefore,
if you increase the circumference by 1 meter, you increase the radius by
1/(2 * pi) meters, or about 0.16 meters.
==> geometry/ham.sandwich.p <==
Consider a ham sandwich, consisting of two pieces of bread and one of
ham. Suppose the sandwich was dropped into a machine and spindled,
torn and mutiliated. Is it still possible to divide the ham sandwich
with a straight knife cut such that both the ham and the bread are
divided in two parts of equal volume?
==> geometry/ham.sandwich.s <==
Yes. There is a theorem in topology called the Ham Sandwich Theorem,
which says: Given 3 (finite) volumes (each may be of any shape, and in
several pieces), there is a plane that cuts each volume in half. One
would learn about it typically in a first course in algebraic topology,
or maybe in a course on introductory topology (if you studied the
fundamental group).
==> geometry/hike.p <==
You are hiking in a half-planar woods, exactly 1 mile from the edge,
when you suddenly trip and lose your sense of direction. What's the
shortest path that's guaranteed to take you out of the woods? Assume
that you can navigate perfectly relative to your current location and
(unknown) heading.
==> geometry/hike.s <==
Go 2/sqrt(3) away from the starting point, turn 120 degrees and head
1/sqrt(3) along a tangent to the unit circle, then traverse an arc of
length 7*pi/6 along this circle, then head off on a tangent 1 mile.
This gives a minimum of sqrt(3) + 7*pi/6 + 1 = 6.397...
It remains to prove this is the optimal answer.
==> geometry/hole.in.sphere.p <==
Old Boniface he took his cheer,
Then he bored a hole through a solid sphere,
Clear through the center, straight and strong,
And the hole was just six inches long.
Now tell me, when the end was gained,
What volume in the sphere remained?
Sounds like I haven't told enough,
But I have, and the answer isn't tough!
==> geometry/hole.in.sphere.s <==
The volume of the leftover material is equal to the volume of a 6" sphere.
First, lets look at the 2 dimensional equivalent of this problem.
Two concentric circles where the chord of the outer circle that is
tangent to the inner circle has length D. What is the area of the "doughnut"
area between the circles?
It is pi * (D/2)^2. The same area as a circle with that diameter.
Proof:
big circle radius is R
little circle radius is r
2 2
area of donut = pi * R - pi * r
2 2
= pi * (R - r )
Draw a right triangle and apply the Pythagorean Theorem to see that
2 2 2
R - r = (D/2)
so the area is
2
= pi * (D/2)
Start with a sphere of radius R (where R > 6"), drill out the 6"
high hole. We will now place this large "ring" on a plane. Next to it
place a 6" high sphere. By Archemedes' theorem, it suffices
to show that for any plane parallel to the base plane, the cross-
sectional area of these two solids is the same.
Take a general plane at height h above (or below) the center
of the solids. The radius of the circle of intersection on the sphere is
radius = srqt(3^2 - h^2)
so the area is
pi * ( 3^2 - h^2 )
For the ring, once again we are looking at the area between two concentric
circles. The outer circle has radius sqrt(R^2 - h^2),
The area of the outer circle is therefore
pi (R^2 - h^2)
The inner circle has
radius sqrt(R^2 - 3^2). So the area of the inner circle is
pi * ( R^2 - 3^2 )
the area of the doughnut is therefore
pi(R^2 - h^2) - pi( R^2 - 3^2 )
= pi (R^2 - h^2 - R^2 + 3^2)
= pi (3^2 - h^2)
Therefore the areas are the same for every plane intersecting the solids.
Therefore their volumes are the same.
QED
==> geometry/ladders.p <==
Two ladders form a rough X in an alley. The ladders are 11 and 13 meters
long and they cross 4 meters off the ground. How wide is the alley?
==> geometry/ladders.s <==
Ladders 1 and 2, denoted L1 and L2, respectively, will rest along two
walls (taken to be perpendicular to the ground), and they will
intersect at a point O = (a,s), a height s from the ground. Find the
largest s such that this is possible. Then find the width of the
alley, w = a+b, in terms of L1, L2, and s. This diagram is not to
scale.
B D
|\ L1 L2 /|
| \ / | BC = length of L1
| \ / | AD = length of L2
| \ O / | s = height of intersection
x| \ / |y A = (0,0)
| /|\ | AE = a
| m / | \ n | EC = b
| / |s \ | AO = m
| / | \ | CO = n
|/________|________\|
(0,0) = A a E b C
-----------------------------------------------------------------------------
Without loss of generality, let L2 >= L1.
Observe that triangles AOB and DOC are similar. Let r be the ratio of
similitude, so that x=ry. Consider right triangles CAB and ACD. By
the Pythagorean theorem, L1^2 - x^2 = L2^2 - y^2. Substituting x=ry,
this becomes y^2(1-r^2) = L2^2 - L1^2. Letting L= L2^2 -L1^2 (L>=0),
and factoring, this becomes
(*) y^2 (1+r)(1-r) = L
Now, because parallel lines cut L1 (a transversal) in proportion, r =
x/y = (L1-n)/n, and so L1/n = r+1. Now, x/s = L1/n = r+1, so ry = x =
s(r+1). Solving for r, one obtains the formula r = s/(y-s).
Substitute this into (*) to get
(**) y^2 (y) (y-2s) = L (y-s)^2
NOTE: Observe that, since L>=0, it must be true that y-2s>=0.
Now, (**) defines a fourth degree polynomial in y. It can be written in the
form (by simply expanding (**))
(***) y^4 - 2s_y^3 - L_y^2 + 2sL_y - Ls^2 = 0
L1 and L2 are given, and so L is a constant. How large can s be? Given L,
the value s=k is possible if and only if there exists a real solution, y',
to (***), such that 2k <= y' < L2. Now that s has been chosen, L and s are
constants, and (***) gives the desired value of y. (Make sure to choose the
value satisfying 2s <= y' < L2. If the value of s is "admissible" (i.e.,
feasible), then there will exist exactly one such solution.)
Now, w = sqrt(L2^2 - y^2), so this concludes the solution.
L1 = 11, L2 = 13, s = 4. L = 13^2-11^2 = 48, so (***) becomes
y^4 - 8_y^3 - 48_y^2 + 384_y - 768 = 0
Numerically find root y ~= 9.70940555, which yields w ~= 8.644504.
==> geometry/lattice/area.p <==
Prove that the area of a triangle formed by three lattice points is integer/2.
==> geometry/lattice/area.s <==
The formula for the area is
A = | x1*y2 + x2*y3 + x3*y1 - x1*y3 - x2*y1 - x3*y2 | / 2
If the xi and yi are integers, A is of the form (integer/2)
==> geometry/lattice/equilateral.p <==
Can an equlateral triangle have vertices at integer lattice points?
==> geometry/lattice/equilateral.s <==
No.
Suppose 2 of the vertices are (a,b) and (c,d), where a,b,c,d are integers.
Then the 3rd vertex lies on the line defined by
(x,y) = 1/2 (a+c,b+d) + t ((d-b)/(c-a),-1) (t any real number)
and since the triangle is equilateral, we must have
||t ((d-b)/(c-a),-1)|| = sqrt(3)/2 ||(c,d)-(a,b)||
which yields t = +/- sqrt(3)/2 (c-a). Thus the 3rd vertex is
1/2 (a+c,b+d) +/- sqrt(3)/2 (d-b,a-c)
which must be irrational in at least one coordinate.
==> geometry/rotation.p <==
What is the smallest rotation that returns an object to its original state?
==> geometry/rotation.s <==
720 degrees.
Objects are made of bosons (integer-spin particles) and fermions
(half-odd-integer spin particles), and the wave function of a fermion
changes sign upon being rotated by 360 degrees. To get it back to its
original state you must rotate by another 360 degrees, for a total of
720 degrees. This fact is the basis of Fermi-Dirac statistics, the
Pauli Exclusion Principle, electron orbits, chemistry, and life.
Mathematically, this is due to the continuous double cover of SO(2) by
SO(3), where SO(2) is the internal symmetry group of fermions and SO(3)
is the group of rotations in three dimensional space.
You can demonstrate this with a tray, which you hold in your right hand
with the arm lowered, then rotate twice as you raise your arm and end
up with the tray above your head, rotated twice about its vertical
axis, but without having twisted your arm.
Also, by attaching strings to a sphere, it is possible to see that a
360 degree rotation will entangle the strings, which another 360 degree
rotation will disentangle.
Hospitals have machines which take out your blood, centrifuge it to take out
certain parts, then return it to your veins. Because of AIDS they must never
let your blood touch the inside of the machine which has touched others'
blood. So the inside is lined with a single piece of disposable branched
plastic tubing. This tube must rotate rapidly in the centrifuge where
several branches come out. Thus the tube should twist and tangle up the
branches. But the machine untwists the branches as in the above discussion.
At several hundred rounds per minute!
References
P. A. M. Dirac's "scissors demonstration"
R. Penrose and W. Rindler
Spinors and Space-time, vol. 1, p. 43
Cambridge University Press, 1984,
R. Feynman and S. Weinberg
Elementary Particles and the Laws of Physics, p. 29
Cambridge University Press, 1987
==> geometry/smuggler.p <==
Somewhere on the high sees smuggler S is attempting, without much
luck, to outspeed coast guard G, whose boat can go faster than S's. G
is one mile east of S when a heavy fog descends. It's so heavy that
nobody can see or hear anything further than a few feet. Immediately
after the fog descends, S changes course and attempts to escape at
constant speed under a new, fixed course. Meanwhile, G has lost track
of S. But G happens to know S's speed, that it is constant, and that S
is sticking to some fixed heading, unknown to G.
How does G catch S?
G may change course and speed at will. He knows his own speed and
course at all times. There is no wind, G does not have radio or radar,
there is enough space for maneuvering, etc.
==> geometry/smuggler.s <==
One way G can catch S is as follows (it is not the fastest way).
G waits until he knows that S has traveled for one mile. At that time, both
S and G are somewhere on a circle with radius one mile, and with its center
at the original position of S. G then begins to travel with a velocity that
has a radially outward component equal to that of S, and with a tangential
component as large as possible, given G's own limitation of total speed. By
doing so, G and S will always both be on an identical circle having its
center at the original position of S. Because G has a tangential component
whereas S does not, G will always catch S (actually, this is not proven
until you solve the o.d.e. associated with the problem).
If G can go at 40 mph and S goes at 20 mph, you can work out that it will
take G at most 1h 49m 52s to catch S. On average, G will catch S in:
( -2pi + sqrt(3) ( exp(2pi/sqrt(3)) - 1 )) / 40pi hours,
which is, 27 min and 17 sec.
==> geometry/table.in.corner.p <==
Put a round table into a (perpendicular) corner so that the table top
touches both walls and the feet are firmly on the ground. If there is
a point on the perimeter of the table, in the quarter circle between
the two points of contact, which is 10 cm from one wall and 5 cm from
the other, what's the diameter of the table?
==> geometry/table.in.corner.s <==
Consider the +X axis and the +Y axis to be the corner. The table has
radius r which puts the center of the circle at (r,r) and makes the
circle tangent to both axis. The equation of the circle (table's
perimeter) is
(x-r)^2 + (y-r)^2 = r^2 .
This leads to
r^2 - 2(x+y) + x^2 + y^2 = 0
Using x = 10, y = 5 we get the solutions 25 and 5. The former is the
radius of the table. It's diameter is 50 cm.
The latter number is the radius of a table that has a point which
satisfies the conditions but is on the outside edge of the table.
==> geometry/tesseract.p <==
If you suspend a cube by one corner and slice it in half with a
horizontal plane through its centre of gravity, the section face is a
hexagon. Now suspend a tesseract (a four dimensional hypercube) by one
corner and slice it in half with a hyper-horizontal hyperplane through
its centre of hypergravity. What is the shape of the section
hyper-face?
==> geometry/tesseract.s <==
The 4-cube is the set of all points in [-1,1]^4 .
The hyperplane { (x,y,z,w) : x + y + z + w = 0 } cuts the 4-cube
in the desired manner.
Now, { (.5,.5,-.5,-.5), (.5,-.5,.5,-.5), (.5,-.5,-.5,.5) } is an
orthonormal basis for the hyperplane. Let (a,b,c) be a point on the
hyperplane with respect to this basis. (a,b,c) is in the 4-cube if and
only if |a| + |b| + |c| <= 2. The shape of the intersection is a
regular octahedron.
==> geometry/tetrahedron.p <==
Suppose you have a sphere of radius R and you have four planes that are
all tangent to the sphere such that they form an arbitrary tetrahedron
(it can be irregular). What is the ratio of the surface area of the
tetrahedron to its volume?
==> geometry/tetrahedron.s <==
For each face of the tetrahedron, construct a new tetrahedron with that
face as the base and the center of the sphere as the fourth vertex.
Now the original tetrahedron is divided into four smaller ones, each of
height R. The volume of a tetrahedron is Ah/3 where A is the area of
the base and h the height; in this case h=R. Combine the four
tetrahedra algebraically to find that the volume of the original
tetrahedron is R/3 times its surface area.
==> geometry/tiling/rational.sides.p <==
A rectangular region R is divided into rectangular areas. Show that if
each of the rectangles in the region has at least one side with
rational length then the same can be said of R.
==> geometry/tiling/rational.sides.s <==
"Fourteen proofs of a result about tiling a rectangle" (Stan Wagon)
_The American Mathematical Monthly_, Aug-Sep 1987, Vol 94 #7. There
was also a fifteenth proof published a few issues later, attributed to
a (University of Kentucky?) student.
==> geometry/tiling/rectangles.with.squares.p <==
Given two sorts of squares, (axa) and (bxb), what rectangles can be tiled?
==> geometry/tiling/rectangles.with.squares.s <==
A rectangle can be tiled with (axa) and (bxb) squares, iff
(i) gcd(a,b)=1 , and any of the following hold:
either: both sides of the rectangle are multiples of a;
or: both sides of the rectangle are multiples of b;
or: one side is a multiple of (ab), and the other is any length EXCEPT
one of a finite number of "bad" lengths: those numbers which are
NOT positive integer combinations of a & b. { By Sylvester's theorem
there are (a-1)(b-1)/2 of these, the largest being (a-1)(b-1)-1. }
(ii) gcd(a,b) = d .
Then merely apply (i) to the problem with a,b replaced
by a/d, b/d and the rectangle lengths also divided by d.
i.e. all cells must appear in (dxd) subsquares.
------
PROOF
It is clear that (ii) follows from (i), and that simple constructions give
the "if" part of (i). For the "only if" part, we prove that...
(S) If one side of the rectangle is not divisible by a, and the other is
not divisible by b, then the tiling is impossible.
The results in (i) follow immediately from (S).
To prove (S): ( Chakraborty-Hoey style ).
~~~~~~~~~~~~~~~~
Let the width of the rectangle be a NON-(a-multiple). Then the number of
bxb squares starting (i.e. top edge) at row 1 must be a NON-a-multiple.
Thus the number of bxb starting at row 2 must BE an a-multiple. Similarly
for the number starting at rows 3,4,...,b . Then the number starting at
row (b+1) must be a NON-a-multiple again.
Similarly the number starting at rows (2b+1), (3b+1), (4b+1),... must all be
non-a-multiples. So if the number of rows is NOT a multiple of b, (call it
bx+r), then row (bx+1) must have a NON-a-multiple of bxb squares starting
there, i.e. at least one, and there is no room left to squeeze it in. [QED]
----
A Rickard-style proof of (S) is ..BBB....BBWWW...WBBB....BBWWW...W(..etc)
~~~~~~~ also possible, by ..BBB....BBWWW...WBBB....BBWWW...W
coloring the rectangle in ..BBB....BBWWW...WBBB....BBWWW...W
vertical strips as shown here: <- a ->< b-a ><- a ->< b-a >
Every square tile covers an a-multiple of black squares. But if the width
is a NON-b-multiple, and the number of rows is a NON-a-multiple, then there
are a NON-a-multiple of black squares in total. [QED]
(Note: the coloring must have 1 column of blacks on the right, and any
==== spare columns of whites on the left.)
===================
Bill Taylor. wft@math.canterbury.ac.nz
>A Rickard-style proof of (S) is ..BBB....BBWWW...WBBB....BBWWW...W(..etc)
> ~~~~~~~ also possible, by ..BBB....BBWWW...WBBB....BBWWW...W
>coloring the rectangle in ..BBB....BBWWW...WBBB....BBWWW...W
>vertical strips as shown here: <- a ->< b-a ><- a ->< b-a >
>
>Every square tile covers an a-multiple of black squares. But if the width
>is a NON-b-multiple, and the number of rows is a NON-a-multiple, then there
>are a NON-a-multiple of black squares in total. [QED]
>
>(Note: the coloring must have 1 column of blacks on the right, and any
> ==== spare columns of whites on the left.)
This statement of how to position the colouring isn't good enough, I'm
afraid. Take a=4, b=7 and consider e.g. a 19x10 rectangle. Coloured your
way, you get:
BWWWBBBBWWWBBBBWWWB
BWWWBBBBWWWBBBBWWWB
:::::::::::::::::::
BWWWBBBBWWWBBBBWWWB
BWWWBBBBWWWBBBBWWWB
The result has 10*10=100 black squares in it, which *is* a multiple of a=4,
despite the fact that 19 is not a multiple of 7 and 10 is not a multiple of
4.
Of course, there is an alternative offset for the pattern that does give you
the result you want:
WWBBBBWWWBBBBWWWBBB
WWBBBBWWWBBBBWWWBBB
:::::::::::::::::::
WWBBBBWWWBBBBWWWBBB
WWBBBBWWWBBBBWWWBBB
To show this happens in general: because the width of the rectangle is a
non-multiple of b, it is possible to position it on the pattern so that the
leftmost column in the rectangle is white and the column just right of the
right edge of the rectangle is black. Suppose N columns are black with this
positioning. Then the rectangle contains N*H black cells, where H is the
height of the rectangle.
If we then shift the rectangle right by one, the number of black columns
increases by 1 and it contains (N+1)*H black cells. The difference between
these two numbers of black cells is H, which is not a multiple of a.
Therefore N*H and (N+1)*H cannot both be multiples of a, and so one of these
two positionings of the pattern will suit your purposes.
David Seal
dseal@armltd.co.uk
==> geometry/tiling/scaling.p <==
A given rectangle can be entirely covered (i.e. concealed) by an
appropriate arrangement of 25 disks of unit radius.
Can the same rectangle be covered by 100 disks of 1/2 unit radius?
==> geometry/tiling/scaling.s <==
Yes. The same configuration of circles, when every distance is reduced
by half (including the diameters), will cover a similar rectangle whose
sides are one half of the original one. The original rectangle is the
union of four such rectangles.
==> geometry/tiling/seven.cubes.p <==
Consider 7 cubes of equal size arranged as follows. Place 5 cubes so
that they form a Swiss cross or a + (plus). ( 4 cubes on the sides and
1 in the middle). Now place one cube on top of the middle cube and the
seventh below the middle cube, to effectively form a 3-dimensional
swiss cross.
Can a number of such blocks (of 7 cubes each) be arranged so that they
are able to completely fill up a big cube (say 10 times the size of
the small cubes)? It is all right if these blocks project out of the
big cube, but there should be no holes or gaps.
==> geometry/tiling/seven.cubes.s <==
Let n be a positive integer. Define the function f from Z^n to Z by
f(x) = x_1+2x_2+3x_3+...+nx_n. For x in Z^n, say y is a neighbor of x
if y and x differ by one in exactly one coordinate. Let S(x) be the
set consisting of x and its 2n neighbors. It is easy to check that
the values of f(y) for y in S(x) are congruent to 0,1,2,...,2n+1 (mod
2n+1) in some order. Using this, it is easy to check that every y in
Z^n is a neighbor of one and only one x in Z^n such that f(x) is
congruent to 0 (mod 2n+1). So Z^n can be tiled by clusters of the
form S(x), where f(x) is congruent to 0 mod 2n+1.
==> group/group.01.p <==
AEFHIKLMNTVWXYZ BCDGJOPQRSU
==> group/group.01.s <==
AEFHIKLMNTVWXYZ drawn with straight lines
BCDGJOPQRSU not drawn with straight lines
==> group/group.01a.p <==
147 0235689
==> group/group.01a.s <==
147 drawn with straight lines
0235689 not drawn with straight lines
==> group/group.02.p <==
ABEHIKMNOPTXZ CDFGJLQRSUVWY
==> group/group.02.s <==
ABEHIKMNOPTXZ resembles Greek letter
CDFGJLQRSUVWY does not resemble Greek letter
==> group/group.03.p <==
BEJQXYZ DFGHLPRU KSTV CO AIW MN
==> group/group.03.s <==
BEJQXYZ no state starting with this letter
DFGHLPRU one state starting with this letter
KSTV two states starting with this letter
CO three states starting with this letter
AIW four states starting with this letter
five states starting with this letter
six states starting with this letter
seven states starting with this letter
MN eight states starting with this letter
==> group/group.04.p <==
BDO P ACGJLMNQRSUVWZ EFTY HIKX
==> group/group.04.s <==
BDO no endpoint
P one endpoint
ACGJLMNQRSUVWZ two endpoints
EFTY three endpoints
HIKX four endpoints
==> group/group.05.p <==
CEFGHIJKLMNSTUVWXYZ ADOPQR B
==> group/group.05.s <==
CEFGHIJKLMNSTUVWXYZ no enclosed area
ADOPQR one enclosed area
B two enclosed areas
==> group/group.06.p <==
BCEGKMQSW DFHIJLNOPRTUVXYZ
==> group/group.06.s <==
BCEGKMQSW prime numbers
DFHIJLNOPRTUVXYZ composites
